JavaGenes: Evolving Graphs with Crossover
Bookreader Item Preview
Share or Embed This Item
texts
JavaGenes: Evolving Graphs with Crossover
- Publication date
- 2000
- Usage
- Public Domain
- Topics
- AERODYNAMIC CHARACTERISTICS, FREQUENCIES, FORCED VIBRATION, FLIGHT SIMULATION, DYNAMIC RESPONSE, ALGORITHMS, AERODYNAMIC CONFIGURATIONS, F-16 AIRCRAFT, FUZZY SYSTEMS, FLIGHT CHARACTERISTICS, UNSTEADY AERODYNAMICS, MODELS, COMPUTERIZED SIMULATION, YAW, STABILITY, ROLL, OSCILLATIONS
- Collection
- nasa_techdocs
- Contributor
- NASA
- Language
- English
- Rights
- Public Domain
Genetic algorithms usually use string or tree representations. We have developed a novel crossover operator for a directed and undirected graph representation, and used this operator to evolve molecules and circuits. Unlike strings or trees, a single point in the representation cannot divide every possible graph into two parts, because graphs may contain cycles. Thus, the crossover operator is non-trivial. A steady-state, tournament selection genetic algorithm code (JavaGenes) was written to implement and test the graph crossover operator. All runs were executed by cycle-scavagging on networked workstations using the Condor batch processing system. The JavaGenes code has evolved pharmaceutical drug molecules and simple digital circuits. Results to date suggest that JavaGenes can evolve moderate sized drug molecules and very small circuits in reasonable time. The algorithm has greater difficulty with somewhat larger circuits, suggesting that directed graphs (circuits) are more difficult to evolve than undirected graphs (molecules), although necessary differences in the crossover operator may also explain the results. In principle, JavaGenes should be able to evolve other graph-representable systems, such as transportation networks, metabolic pathways, and computer networks. However, large graphs evolve significantly slower than smaller graphs, presumably because the space-of-all-graphs explodes combinatorially with graph size. Since the representation strongly affects genetic algorithm performance, adding graphs to the evolutionary programmer's bag-of-tricks should be beneficial. Also, since graph evolution operates directly on the phenotype, the genotype-phenotype translation step, common in genetic algorithm work, is eliminated.
- Addeddate
- 2011-05-29 04:01:50
- Document-source
- CASI
- Documentid
- 20000115611
- Identifier
- nasa_techdoc_20000115611
- Identifier-ark
- ark:/13960/t1gj0ch9j
- Nasa-center
- Ames Research Center
- Ocr
- ABBYY FineReader 8.0
- Online-source
- http://wayback.archive-it.org/1792/20100201093141/http://hdl.handle.net/2060/20000115611
- Original-nasa-rights
- Unclassified; Copyright (Distribution as joint owner in the copyright) ; Unlimited; Publicly available;
- Ppi
- 300
- Report-number
- AIAA Paper 2000-3910
- Updated-added-to-ntrs
- 2009-07-29
- Year
- 2000
comment
Reviews
There are no reviews yet. Be the first one to
write a review.
275 Views
DOWNLOAD OPTIONS
For users with print-disabilities
IN COLLECTIONS
NASA Technical DocumentsUploaded by Greg Williamson on